最小的K个数

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        for i in range(1, len(input)):
            j = i - 1
            tmp = input[i]
            while j >= 0 and input[j] > tmp:
                input[j+1] = input[j]
                j -= 1
            input[j+1] = tmp
        return input[:k]

保留最小k个，应维护容量为k的大顶堆，若超过k个，则立刻pop出最大的数字，最后剩余k个就是最小的

牛客C#没有优先队列，跑来写Python
结果发现Python没有大顶堆，只能使用小顶堆*-1丑陋操作

import heapq
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        max_heap = []
        if k == 0:
            return max_heap

        for num in input:
            #不足k个或更小
            if len(max_heap) < k:
                heapq.heappush(max_heap, -num)
            else:
                heapq.heappushpop(max_heap, -num) # 自动淘汰最大的数字

        return [i * -1 for i in max_heap]

# 维护一个k个元素的大顶堆，堆顶元素是k个元素的最大值，每来一个新元素时，判断其与堆顶元素的关系：若新元素比堆顶元素小，那么用该元素替换堆顶元素，同时更新最大堆
class maxHeap(object):
    def __init__(self, k):
        self._stack = []
        self._count = 0
        self.k = k

    def size(self):
        return self._count

    def getAllElement(self):
        return self._stack

    def add(self, x):
        # 先判断当前堆元素是否已满
        if self.size() < self.k:
            self._stack.append(x)
            self._shift_up(self._count)
            self._count += 1
        # 若当前堆元素已满
        else:
            if x < self.peak():
                self._stack[0] = x
                self._shift_down(0)
            
    def peak(self):
        return self._stack[0] if self._stack else None

    # 从最后一个节点开始往上更新
    def _shift_up(self, index):
        parent = (index - 1) >> 1
        while index > 0 and self._stack[index] > self._stack[parent]:
            self._stack[index], self._stack[parent] = self._stack[parent], self._stack[index]
            index = parent
            parent = (index - 1) >> 1

    
    # 从第一个节点开始往下更新 
    def _shift_down(self, index):
        max_child = (index << 1) + 1
        # 先判断一下左右节点哪个更大一些
        if max_child + 1 < self._count and self._stack[max_child + 1] > self._stack[max_child]:
            max_child += 1
        while max_child < self._count and self._stack[index] < self._stack[max_child]:
            self._stack[index], self._stack[max_child] = self._stack[max_child], self._stack[index]
            index = max_child
            max_child = (index << 1) + 1
            if max_child + 1 < self._count and self._stack[max_child + 1] > self._stack[max_child]:
                    max_child += 1


class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        if k <= 0:
            return None
        max_heap = maxHeap(k)
        for num in input:
            max_heap.add(num)

        return max_heap.getAllElement()

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        if not input: return None
        if k > len(input): return None
        input.sort()
        return input[0:k]

快排思想
class Solution:
    def partition(self, a, low, high):
        temp = a[low]
        while low < high:
            while low < high and a[high] > temp:
                high -= 1
            a[low] = a[high]
            while low < high and a[low] <= temp:
                low += 1
            a[high] = a[low]
        a[low] = temp
        return low

    def quick_sort(self, a, low, high, k):
        p =self.partition(a, low, high)
        if p-low+1 == k:
            return a[:p+1]
        elif p-low+1 > k:
            return self.quick_sort(a, low, p-1, k)
        else:
            return self.quick_sort(a, p+1, high, k-(p-low+1))

    def GetLeastNumbers_Solution(self , input_: List[int], k: int) -> List[int]:
        n = len(input_)
        if k > n or n == 0 or k == 0:
            return []
        return self.quick_sort(input_, 0, len(input_)-1, k)

class Solution:
   # 利用堆排序 最小堆  
    def minFixHeap(self,t,i,n):
        # 最小堆调整
        tmp = t[i]
        j = i*2 + 1
        while j < n:
            # 找出左右叶子节点较小值
            if j+1 < n and t[j] > t[j+1]:
                j = j + 1
            # 找出根和叶子节点的最小值
            if tmp > t[j]:
                t[i] = t[j]  # 最小值放在根上
                i = j
                j = i*2 + 1
            else:
                break
        t[i] = tmp

    def GetLeastNumbers_Solution(self, tinput, k):
        lens = len(tinput)
        if k>lens or k <0 or lens ==0:
            return []
        # 从最后一个非叶子节点开始调整，反复调用筛选过程，直到第一个节点，则得到一个堆
        for i in range(lens//2,-1,-1):
            self.minFixHeap(tinput,i,lens)

        res = []
        for i in range(lens-1,lens-k-1,-1):
            res.append(tinput[0])
            # 将最后的叶子节点放到根节点，重新进行最小堆调整
            tinput[0] = tinput[i]  
            self.minFixHeap(tinput,0,i)
        return res

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        in_data=sorted(input)
        if k>0:
            return in_data[:k]
        else:
            return []

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        return sorted(input)[:k]

    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        input.sort()
        return [input[i] for i in range(k)]

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        def heapfiy(array, index, length):
            left = 2 * index + 1
            right = 2 * index + 2
            temp = index
            if left < length and array[temp] < array[left]:
                temp = left
            if right < length and array[temp] < array[right]:
                temp = right
            if temp != index:
                array[index], array[temp] = array[temp], array[index]
                heapfiy(array, temp, length)
        for i in range((k - 1) // 2, -1, -1):
            heapfiy(input, i, k)
        for i in range(k, len(input)):
            if input[i] < input[0]:
                input[i], input[0] = input[0], input[i]
                heapfiy(input, 0, k)
        return input[:k]